#ifndef STX_ALGORITHM_BINARY_SEARCH_HPP
#define STX_ALGORITHM_BINARY_SEARCH_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/lower_bound.hpp>

namespace stx {

template <class Compare, class ForwardIterator, class T>
inline bool
binary_search_impl(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
    first = lower_bound_impl<Compare>(first, last, value, comp);
    return first != last && !comp(value, *first);
}

template <class ForwardIterator, class T, class Compare>
inline bool
binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return binary_search_impl<comp_ref>(first, last, value, comp);
}

template <class ForwardIterator, class T>
inline bool
binary_search(ForwardIterator first, ForwardIterator last, const T& value)
{
    return stx::binary_search(
        first,
        last,
        value,
        stx::less<typename std::iterator_traits<ForwardIterator>::value_type, T>());
}

} // namespace stx

#endif // STX_ALGORITHM_BINARY_SEARCH_HPP
